package com.code.test.second.array;

import java.util.Arrays;

public class SCode704 {
    public static void main(String[] args) {
        int[] nums = {-1, 0, 3, 5, 9, 12};
        int target = 9;
        int ret;
//        int ret = search(nums, target);
//        System.out.println(ret);
//
//        ret = search(nums, 4);
//        System.out.println(ret);

        /**
         * =================================
         */

//        int[] newnums = {-1, 0, 3, 3, 5, 9, 12, 3};
//
//        ret = searchFirst(newnums, 3);
//        System.out.println(ret);

        int[] lastnums = {-1, 0, 3, 3, 5, 9, 12, 3};

        ret = searchLast(lastnums, 3);
        System.out.println(ret);


    }

    /**
     * 二分查找，
     * 不重复
     */
    public static int search(int[] nums, int target) {
        //从小到大排序
        Arrays.sort(nums);

        int len = nums.length;
        int low = 0;
        int high = len - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                //如果中间值比目标值小，代表目标值在右侧
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }

    /**
     * 重复,找到第一个匹配的元素
     */
    public static int searchFirst(int[] nums, int target) {
        //从小到大排序
        Arrays.sort(nums);

        int len = nums.length;
        int low = 0;
        int high = len - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (nums[mid] < target) {
                //如果中间值比目标值小，代表目标值在右侧
                low = mid + 1;
            } else if (nums[mid] > target) {
                high = mid - 1;
            } else {
                //这里是等于的情况下，如果前一个不等于target，则找到的就是mid
                if (mid == 0 || nums[mid - 1] != target) {
                    return mid;
                } else {
                    //因为中间值已经等于目标值，且是从小到大排序，且要找的是第一个匹配，所以这边还要继续往左边找
                    high = mid - 1;
                }
            }
        }
        return -1;
    }

    /**
     * 重复,找到最后匹配的元素
     */
    public static int searchLast(int[] nums, int target) {
        //从小到大排序
        Arrays.sort(nums);

        int len = nums.length;
        int low = 0;
        int high = len - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (nums[mid] < target) {
                //如果中间值比目标值小，代表目标值在右侧
                low = mid + 1;
            } else if (nums[mid] > target) {
                high = mid - 1;
            } else {
                //这里是等于的情况下，如果后一个不等于target(因为排过序了)，则找到的就是mid
                if (mid == 0 || nums[mid + 1] != target) {
                    return mid;
                } else {
                    //因为中间值已经等于目标值，且是从小到大排序，且要找的是最后一个匹配，所以这边还要继续往右边找
                    low = mid + 1;
                }
            }
        }
        return -1;
    }


}
